"""
难度：中等
给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。】
但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：s = "ababccc"
输出：5
解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。
示例 2：
输入：s = "aba"
输出：2
解释：一种最大拆分方法为 ['a', 'ba'] 。
示例 3：
输入：s = "aa"
输出：1
解释：无法进一步拆分字符串。
"""
class Solution:
    ans = 0
    def maxUniqueSplit(self, s: str) -> int:
        s_set = set()
        self.ans = 0
        self.backtrack(s, 0, 0, s_set)
        return self.ans


    def backtrack(self, s, index, count, s_set):
        if len(s) - index + count <= self.ans:
            return
        if index >= len(s):
            self.ans = max(self.ans, count)
            return
        for i in range(index, len(s)):
            sub_s = s[index: i + 1]
            if sub_s not in s_set:
                s_set.add(sub_s)
                self.backtrack(s, i +1 , count + 1, s_set)
                s_set.remove(sub_s)
            



class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def backtrack(index: int, split: int):
            if index >= length:
                nonlocal maxSplit
                maxSplit = max(maxSplit, split)
            else:
                for i in range(index, length):
                    substr = s[index:i+1]
                    if substr not in seen:
                        seen.add(substr)
                        backtrack(i + 1, split + 1)
                        seen.remove(substr)

        length = len(s)
        seen = set()
        maxSplit = 1
        backtrack(0, 0)
        return maxSplit